package com.zdb.datastructures.queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {

    public static void main(String[] args) {

        CircleArrayQueue queue = new CircleArrayQueue(4);
        // 接收用户输入
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        // 输出菜单
        while(loop) {
            System.out.println("----- 操作指南 ------");
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列中取出数据");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0);
            switch (key) {
            case 's':
                queue.showQueue();
                break;
            case 'a':
                System.out.println("请输入需要加入队列的数：");
                int v = scanner.nextInt();
                queue.addQueue(v);
                break;
            case 'g':
                try {
                    int res = queue.getQueue();
                    System.out.printf("取出的数据为%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'h':
                try {
                    int res = queue.headQueue();
                    System.out.printf("队列头的数据为%d\n", res);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;
            case 'e':
                scanner.close();
                loop = false;
                System.out.println("程序退出~~");
                break;
            default:
                System.out.println("异常输入："+ key);

            }
        }

    }
}

/**
 * 使用环形数组来制作队列
 *
 * 留一个空位来约定
 *
 */
class CircleArrayQueue {

    // 内部数组的长度，最大可存放数据个数为 maxSize -1;
    private int maxSize;
    // 当front != rear时，代表队列的第一个元素的数组下标
    private int front;
    // 队列中下一个存放数据的下标，该位置一直为空，
    // 所以当(rear+1)%maxSize == front时，队列满了,rear的判断优先级高
    private int rear;
    private int[] arr;

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = 0;
        rear = 0;
    }

    /**
     * 当 (rear + 1) % maxSize == front，说明队列已满
     * @return
     */
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * 当rear等于front时，说明front为空，此时队列为空
     * @return
     */
    public boolean isEmpty() {
        return front == rear;
    }

    public void addQueue(int n) {

        if(isFull()) {
            System.out.println("队列已满，不能添加元素~~");
            return;
        }
        arr[rear] = n;
        rear = (rear + 1) % maxSize;
    }

    public int getQueue() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空，不能取出元素~~");
        }
        // 保存front的元素
        int tmp = arr[front];

        front = (front + 1) % maxSize;

        return tmp;
    }

    public int headQueue() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空，头元素为空");
        }
        return arr[front];
    }

    /**
     * 打印队列中所有元素
     *
     * front -> front + (队列中元素个数)
     */
    public void showQueue() {

        System.out.println("------ 打印队列如下：");
        int size = size();
        for(int i=front; i< front + size; i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i%maxSize]);
        }

    }

    private int size() {
        return (rear + maxSize - front)% maxSize;
    }
}
